<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>


<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">



  <meta name="description" content="痛苦的数据结构OJ续"/>




  <meta name="keywords" content="c++, 算法, OJ, 八一" />



  <meta name="baidu-site-verification" content="HhUstaSjr0" />



  <meta name="google-site-verification" content="UA-102975942-1" />






  <link rel="alternate" href="/atom.xml" title="八一">




  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=2.6.0" />



<link rel="canonical" href="https://bay1.top/2017/05/27/痛苦的数据结构OJ续/"/>


<link rel="stylesheet" type="text/css" href="/css/style.css?v=2.6.0" />
<link rel="stylesheet" type="text/css" href="/css/prettify.css" media="screen" />
<link rel="stylesheet" type="text/css" href="/css/sons-of-obsidian.css" media="screen" />



  <link rel="stylesheet" type="text/css" href="/lib/fancybox/jquery.fancybox.css" />




  
  <script id="baidu_analytics">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?9a885cc9fb6cd7bcef579deb8efe8a70";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>



  <script id="google_analytics">
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

        ga('create', 'UA-102975942-1', 'auto');
        ga('send', 'pageview');
  </script>










    <title> 痛苦的数据结构OJ续 - 八一 </title>
  </head>

  <body><div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/." class="logo">八一</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>

<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    
      <a href="/archives">
        <li class="mobile-menu-item">
          
          
            文章
          
        </li>
      </a>
    
      <a href="/tags">
        <li class="mobile-menu-item">
          
          
            标签
          
        </li>
      </a>
    
      <a href="/about">
        <li class="mobile-menu-item">
          
          
            关于/友链
          
        </li>
      </a>
    
      <a href="/search">
        <li class="mobile-menu-item">
          
          
            站内搜索
          
        </li>
      </a>
    
  </ul>
</nav>

    <div class="container" id="mobile-panel">
      <header id="header" class="header"><div class="logo-wrapper">
  <a href="/." class="logo">八一</a>
</div>

<nav class="site-navbar">
  
    <ul id="menu" class="menu">
      
        <li class="menu-item">
          <a class="menu-item-link" href="/archives">
            
            
              文章
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/tags">
            
            
              标签
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/about">
            
            
              关于/友链
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/search">
            
            
              站内搜索
            
          </a>
        </li>
      
    </ul>
  
</nav>

      </header>

      <main id="main" class="main">
        <div class="content-wrapper">
          <div id="content" class="content">
            
  
  <article class="post">
    <header class="post-header">
      <h1 class="post-title">
        
          痛苦的数据结构OJ续
        
      </h1>

      <div class="post-meta">
        <span class="post-time">
          2017-05-27
        </span>
        
        
        
      </div>
    </header>

    
    
  <div class="post-toc" id="post-toc">
    <h2 class="post-toc-title">文章目录</h2>
    <div class="post-toc-content">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#Let-the-Balloon-Rise"><span class="toc-text">Let the Balloon Rise</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Elevator"><span class="toc-text">Elevator</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#彩色字符串"><span class="toc-text">彩色字符串</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#愚人节的礼物"><span class="toc-text">愚人节的礼物</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#迷宫"><span class="toc-text">迷宫</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#表达式求值"><span class="toc-text">表达式求值</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#n阶Hanoi塔问题"><span class="toc-text">n阶Hanoi塔问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#定位子串"><span class="toc-text">定位子串</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#字符串插入"><span class="toc-text">字符串插入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#求子串位置的定位函数"><span class="toc-text">求子串位置的定位函数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#KMP算法中的模式串移动数组"><span class="toc-text">KMP算法中的模式串移动数组</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#KMP字符串模式匹配算法实现"><span class="toc-text">KMP字符串模式匹配算法实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#稀疏矩阵转置"><span class="toc-text">稀疏矩阵转置</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#稀疏矩阵快速转置"><span class="toc-text">稀疏矩阵快速转置</span></a></li></ol>
    </div>
  </div>


    <div class="post-content">
      
        <p>数据结构的OJ题目为什么更新这么频繁。。。。<a id="more"></a></p>
<blockquote>
<p>下面的代码有我写的，有搜索之后修改的，。。。但是这么难的题，大部分都还是修改的(那些代码超级长的题)。</p>
</blockquote>
<h2 id="Let-the-Balloon-Rise"><a href="#Let-the-Balloon-Rise" class="headerlink" title="Let the Balloon Rise"></a>Let the Balloon Rise</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> &#123;</span></span><br><span class="line">	<span class="keyword">char</span> x;</span><br><span class="line">	<span class="keyword">int</span> i;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="keyword">bool</span> <span class="keyword">operator</span>&lt;(node a, node b) &#123;</span><br><span class="line">	<span class="keyword">return</span> a.x &gt; b.x;</span><br><span class="line">&#125;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Set</span>&#123;</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	<span class="keyword">char</span> s[<span class="number">1050</span>][<span class="number">30</span>];</span><br><span class="line">	<span class="keyword">char</span> n;</span><br><span class="line">	<span class="keyword">int</span> num[<span class="number">1050</span>];</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	Set() &#123;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">1050</span>; i++) &#123;</span><br><span class="line">			<span class="built_in">strcpy</span>(s[i], <span class="string">""</span>);</span><br><span class="line">			num[i] = <span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		n = <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">char</span> *name)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </span><br><span class="line">			<span class="keyword">if</span> (! <span class="built_in">strcmp</span>(s[i], name))</span><br><span class="line">				<span class="keyword">return</span> i;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">char</span> *name)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span> i = find(name);</span><br><span class="line">		<span class="keyword">if</span> (i &gt;= <span class="number">0</span>) </span><br><span class="line">			num[i]++;</span><br><span class="line">		<span class="keyword">else</span> </span><br><span class="line">			<span class="built_in">strcpy</span>(s[n++], name);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">show</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span> max = <span class="number">0</span>;</span><br><span class="line">		priority_queue&lt;node&gt; q;</span><br><span class="line">		node x;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (max &lt; num[i]) &#123;</span><br><span class="line">				max = num[i];</span><br><span class="line">				<span class="keyword">while</span> (! q.empty()) &#123;</span><br><span class="line">					q.pop();</span><br><span class="line">				&#125;</span><br><span class="line">				x.x = s[i][<span class="number">0</span>];</span><br><span class="line">				x.i = i;</span><br><span class="line">				q.push(x);</span><br><span class="line">			&#125; <span class="keyword">else</span> <span class="keyword">if</span> (max == num[i])&#123;</span><br><span class="line">				x.x = s[i][<span class="number">0</span>];</span><br><span class="line">				x.i = i;</span><br><span class="line">				q.push(x);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">while</span> (! q.empty()) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; s[q.top().i] &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">			q.pop();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	<span class="keyword">char</span> name[<span class="number">30</span>];</span><br><span class="line">	<span class="keyword">while</span> ((<span class="built_in">cin</span> &gt;&gt; n) &amp;&amp; n) &#123;</span><br><span class="line">		Set s;</span><br><span class="line">		<span class="keyword">while</span> (n--) &#123;</span><br><span class="line">			<span class="built_in">cin</span> &gt;&gt; name;</span><br><span class="line">			s.insert(name);</span><br><span class="line">		&#125;</span><br><span class="line">		s.show();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="Elevator"><a href="#Elevator" class="headerlink" title="Elevator"></a>Elevator</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;  </span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;  </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> x[<span class="number">10000</span>]=&#123;<span class="number">0</span>&#125;,t,m;  </span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;m)  </span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="keyword">if</span>(m!=<span class="number">0</span>)  </span><br><span class="line">        &#123;  </span><br><span class="line">            t=<span class="number">0</span>;  </span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)  </span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">cin</span>&gt;&gt;x[i];  </span><br><span class="line">                <span class="keyword">if</span>(x[i<span class="number">-1</span>]&lt;x[i])  </span><br><span class="line">                &#123;  </span><br><span class="line">                    t+=(x[i]-x[i<span class="number">-1</span>])*<span class="number">6</span>;  </span><br><span class="line">                &#125;  </span><br><span class="line">                <span class="keyword">if</span>(x[i<span class="number">-1</span>]&gt;x[i])  </span><br><span class="line">                &#123;  </span><br><span class="line">                    t+=(x[i<span class="number">-1</span>]-x[i])*<span class="number">4</span>;  </span><br><span class="line">                &#125;  </span><br><span class="line">                t+=<span class="number">5</span>;  </span><br><span class="line">            &#125;  </span><br><span class="line">            <span class="built_in">cout</span>&lt;&lt;t&lt;&lt;<span class="built_in">endl</span>;  </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> </span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="彩色字符串"><a href="#彩色字符串" class="headerlink" title="彩色字符串"></a>彩色字符串</h2><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include &lt;cstdio&gt;</span><br><span class="line">#include &lt;stack&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">int <span class="function"><span class="title">fun</span><span class="params">(char x)</span></span> &#123;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'('</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'&lt;'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'['</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">']'</span> || x == <span class="string">')'</span> || x == <span class="string">'&gt;'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line">int ans[<span class="number">5</span>];</span><br><span class="line">int main() &#123;</span><br><span class="line">	int n,idx;</span><br><span class="line">	char x;</span><br><span class="line">	cin &gt;&gt; n;</span><br><span class="line">	getchar();</span><br><span class="line">	<span class="keyword">while</span> (n--) &#123;</span><br><span class="line">		stack&lt;char&gt; s;</span><br><span class="line">		ans[<span class="number">1</span>] = ans[<span class="number">2</span>] = ans[<span class="number">3</span>] = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (<span class="number">1</span>) &#123;</span><br><span class="line">			x = getchar();</span><br><span class="line">			<span class="keyword">if</span> (x == <span class="string">'\n'</span>) &#123;</span><br><span class="line">				cout &lt;&lt; ans[<span class="number">1</span>] &lt;&lt; <span class="string">" "</span> &lt;&lt; ans[<span class="number">2</span>] &lt;&lt; <span class="string">" "</span> &lt;&lt; ans[<span class="number">3</span>] &lt;&lt; endl;</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> (! <span class="function"><span class="title">fun</span><span class="params">(x)</span></span>)</span><br><span class="line">				ans[idx]++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (<span class="function"><span class="title">fun</span><span class="params">(x)</span></span> &gt; <span class="number">0</span>) &#123;</span><br><span class="line">				s.push(x);</span><br><span class="line">				idx = <span class="function"><span class="title">fun</span><span class="params">(x)</span></span>;</span><br><span class="line">			&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">				s.pop();</span><br><span class="line">				<span class="keyword">if</span> (! s.empty())</span><br><span class="line">					idx = <span class="function"><span class="title">fun</span><span class="params">(s.top()</span></span>);</span><br><span class="line">				<span class="keyword">else</span></span><br><span class="line">					idx = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="愚人节的礼物"><a href="#愚人节的礼物" class="headerlink" title="愚人节的礼物"></a>愚人节的礼物</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">char</span> a[<span class="number">1010</span>];</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span>&gt;&gt;a) &#123;</span><br><span class="line">		<span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">int</span> num=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (a[i]!=<span class="string">'\0'</span>) &#123;</span><br><span class="line">			<span class="keyword">if</span> (a[i]==<span class="string">'('</span>) &#123;</span><br><span class="line">				num++;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(a[i]==<span class="string">')'</span>)&#123;</span><br><span class="line">				num--;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="built_in">cout</span>&lt;&lt;num&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="迷宫"><a href="#迷宫" class="headerlink" title="迷宫"></a>迷宫</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;string.h&gt;  </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;ctype.h&gt;  </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;malloc.h&gt;   </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;limits.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;  </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> TRUE 1  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> FALSE 0  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK 1  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR 0  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INFEASIBLE -1  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OVERFLOW 0  </span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Status; </span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Boolean; </span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXLENGTH 25  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> STACK_INIT_SIZE 10</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> STACKINCREMENT 2 </span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>  </span></span><br><span class="line"><span class="class">&#123;</span>  </span><br><span class="line">    <span class="keyword">int</span> r, c;</span><br><span class="line">&#125; PosType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>  </span></span><br><span class="line"><span class="class">&#123;</span>  </span><br><span class="line">    <span class="keyword">int</span> ord;</span><br><span class="line">    PosType seat;</span><br><span class="line">    <span class="keyword">int</span> di;  </span><br><span class="line">&#125; SElemType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>  </span></span><br><span class="line"><span class="class">&#123;</span>  </span><br><span class="line">    SElemType * base; </span><br><span class="line">    SElemType * top;</span><br><span class="line">    <span class="keyword">int</span> stacksize;</span><br><span class="line">&#125; SqStack;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>  </span></span><br><span class="line"><span class="class">&#123;</span>  </span><br><span class="line">    <span class="keyword">char</span> arr[<span class="number">10</span>][<span class="number">11</span>];  </span><br><span class="line">&#125; MazeType;</span><br><span class="line"><span class="function">Status <span class="title">Pass</span><span class="params">(MazeType MyMaze, PosType CurPos)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span> (MyMaze.arr[CurPos.r][CurPos.c]==<span class="string">' '</span> || MyMaze.arr[CurPos.r][CurPos.c]==<span class="string">'S'</span> || MyMaze.arr[CurPos.r][CurPos.c]==<span class="string">'E'</span>)  </span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span>  </span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>; </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">FootPrint</span><span class="params">(MazeType &amp;MyMaze, PosType CurPos)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    MyMaze.arr[CurPos.r][CurPos.c] = <span class="string">'*'</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function">PosType <span class="title">NextPos</span><span class="params">(PosType CurPos, <span class="keyword">int</span> Dir)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    PosType ReturnPos;  </span><br><span class="line">    <span class="keyword">switch</span> (Dir)  </span><br><span class="line">    &#123;  </span><br><span class="line">    <span class="keyword">case</span> <span class="number">1</span>:  </span><br><span class="line">        ReturnPos.r = CurPos.r;  </span><br><span class="line">        ReturnPos.c = CurPos.c + <span class="number">1</span>;  </span><br><span class="line">        <span class="keyword">break</span>;  </span><br><span class="line">    <span class="keyword">case</span> <span class="number">2</span>:  </span><br><span class="line">        ReturnPos.r = CurPos.r + <span class="number">1</span>;  </span><br><span class="line">        ReturnPos.c = CurPos.c;  </span><br><span class="line">        <span class="keyword">break</span>;  </span><br><span class="line">    <span class="keyword">case</span> <span class="number">3</span>:  </span><br><span class="line">        ReturnPos.r = CurPos.r;  </span><br><span class="line">        ReturnPos.c = CurPos.c - <span class="number">1</span>;  </span><br><span class="line">        <span class="keyword">break</span>;  </span><br><span class="line">    <span class="keyword">case</span> <span class="number">4</span>:  </span><br><span class="line">        ReturnPos.r = CurPos.r - <span class="number">1</span>;  </span><br><span class="line">        ReturnPos.c = CurPos.c;  </span><br><span class="line">        <span class="keyword">break</span>;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">return</span> ReturnPos;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">MarkPrint</span><span class="params">(MazeType &amp;MyMaze, PosType CurPos)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    MyMaze.arr[CurPos.r][CurPos.c] = <span class="string">'!'</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function">Status <span class="title">InitStack</span><span class="params">(SqStack *S)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    (*S).base=(SElemType *)<span class="built_in">malloc</span>(STACK_INIT_SIZE*<span class="keyword">sizeof</span>(SElemType));  </span><br><span class="line">    <span class="keyword">if</span>(!(*S).base)  </span><br><span class="line">        <span class="built_in">exit</span>(OVERFLOW);  </span><br><span class="line">    (*S).top=(*S).base;  </span><br><span class="line">    (*S).stacksize=STACK_INIT_SIZE;  </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="function">Status <span class="title">Push</span><span class="params">(SqStack *S,SElemType e)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>((*S).top-(*S).base&gt;=(*S).stacksize)</span><br><span class="line">    &#123;  </span><br><span class="line">        (*S).base=(SElemType *)<span class="built_in">realloc</span>((*S).base,((*S).stacksize+STACKINCREMENT)*<span class="keyword">sizeof</span>(SElemType));  </span><br><span class="line">        <span class="keyword">if</span>(!(*S).base)  </span><br><span class="line">            <span class="built_in">exit</span>(OVERFLOW);</span><br><span class="line">        (*S).top=(*S).base+(*S).stacksize;  </span><br><span class="line">        (*S).stacksize+=STACKINCREMENT;  </span><br><span class="line">    &#125;  </span><br><span class="line">    *((*S).top)++=e;  </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function">Status <span class="title">StackEmpty</span><span class="params">(SqStack S)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(S.top==S.base)  </span><br><span class="line">        <span class="keyword">return</span> TRUE;  </span><br><span class="line">    <span class="keyword">else</span>  </span><br><span class="line">        <span class="keyword">return</span> FALSE;  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="function">Status <span class="title">Pop</span><span class="params">(SqStack *S,SElemType *e)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>((*S).top==(*S).base)  </span><br><span class="line">        <span class="keyword">return</span> ERROR;  </span><br><span class="line">    *e=*--(*S).top;  </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function">Status <span class="title">MazePath</span><span class="params">(MazeType &amp;maze, PosType start, PosType end)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    SqStack S;  </span><br><span class="line">    PosType curpos;  </span><br><span class="line">    <span class="keyword">int</span> curstep;  </span><br><span class="line">    SElemType e;  </span><br><span class="line">    InitStack(&amp;S);  </span><br><span class="line">    curpos = start;</span><br><span class="line">    curstep = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">do</span>  </span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="keyword">if</span> (Pass(maze, curpos))</span><br><span class="line">        &#123;  </span><br><span class="line">            FootPrint(maze, curpos);</span><br><span class="line">            e.di = <span class="number">1</span>;  </span><br><span class="line">            e.ord = curstep;  </span><br><span class="line">            e.seat = curpos;  </span><br><span class="line">            Push(&amp;S, e);</span><br><span class="line">            <span class="keyword">if</span> (curpos.r == end.r &amp;&amp; curpos.c == end.c)  </span><br><span class="line">                <span class="keyword">return</span> (TRUE);  </span><br><span class="line">            curpos = NextPos(curpos, <span class="number">1</span>); </span><br><span class="line">            curstep++; </span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="keyword">else</span>  </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="keyword">if</span> (!StackEmpty(S))  </span><br><span class="line">            &#123;  </span><br><span class="line">                Pop(&amp;S, &amp;e);  </span><br><span class="line">                <span class="keyword">while</span> (e.di == <span class="number">4</span> &amp;&amp; !StackEmpty(S))  </span><br><span class="line">                &#123;  </span><br><span class="line">                    MarkPrint(maze, e.seat);  </span><br><span class="line">                    Pop(&amp;S, &amp;e); </span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (e.di &lt; <span class="number">4</span>)  </span><br><span class="line">                &#123;  </span><br><span class="line">                    e.di++;  </span><br><span class="line">                    Push(&amp;S, e);</span><br><span class="line">                    curpos = NextPos(e.seat, e.di);</span><br><span class="line">                &#125; </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">while</span> (!StackEmpty(S));  </span><br><span class="line">    <span class="keyword">return</span> FALSE;  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> i, j;  </span><br><span class="line">    PosType start, end; </span><br><span class="line">    MazeType maze; </span><br><span class="line">    <span class="built_in">memset</span>(maze.arr, <span class="number">0</span>, <span class="keyword">sizeof</span>(maze.arr)); </span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;<span class="number">10</span>; i++) </span><br><span class="line">    &#123;  </span><br><span class="line">        gets(maze.arr[i]);  </span><br><span class="line">        <span class="keyword">for</span>(j=<span class="number">0</span>; j&lt;<span class="number">10</span>; j++)  </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="keyword">if</span>(maze.arr[i][j] == <span class="string">'S'</span>)</span><br><span class="line">            &#123;  </span><br><span class="line">                start.r = i;  </span><br><span class="line">                start.c = j;  </span><br><span class="line">            &#125;  </span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(maze.arr[i][j] == <span class="string">'E'</span>)</span><br><span class="line">            &#123;  </span><br><span class="line">                end.r = i;  </span><br><span class="line">                end.c = j;  </span><br><span class="line">            &#125;  </span><br><span class="line">        &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    MazePath(maze, start, end);</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;<span class="number">10</span>; i++)</span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="built_in">puts</span>(maze.arr[i]);  </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="表达式求值"><a href="#表达式求值" class="headerlink" title="表达式求值"></a>表达式求值</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">isp</span><span class="params">(<span class="keyword">char</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'#'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'('</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'*'</span> || x == <span class="string">'/'</span> || x == <span class="string">'%'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">5</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'+'</span> || x == <span class="string">'-'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">')'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">6</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">icp</span><span class="params">(<span class="keyword">char</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'#'</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'('</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">6</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'*'</span> || x == <span class="string">'/'</span> || x == <span class="string">'%'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">4</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'+'</span> || x == <span class="string">'-'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">')'</span>)</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">fun</span><span class="params">(<span class="keyword">double</span> a, <span class="keyword">double</span> b, <span class="keyword">char</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'+'</span>)</span><br><span class="line">		<span class="keyword">return</span> a + b;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'-'</span>)</span><br><span class="line">		<span class="keyword">return</span> a - b;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'*'</span>)</span><br><span class="line">		<span class="keyword">return</span> a * b;</span><br><span class="line">	<span class="keyword">if</span> (x == <span class="string">'/'</span>)</span><br><span class="line">		<span class="keyword">return</span> a / b;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span> <span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> x;</span><br><span class="line">	<span class="keyword">int</span> n = <span class="number">0</span>;</span><br><span class="line">	<span class="built_in">stack</span>&lt;<span class="keyword">char</span>&gt; op;</span><br><span class="line">	<span class="built_in">stack</span>&lt;<span class="keyword">double</span>&gt; num;</span><br><span class="line">	op.push(<span class="string">'#'</span>);</span><br><span class="line">	<span class="keyword">double</span> a, b;</span><br><span class="line">	<span class="built_in">queue</span>&lt;<span class="keyword">int</span>&gt; q;</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; x) &#123;</span><br><span class="line">		<span class="keyword">if</span> (x &gt;= <span class="string">'0'</span> &amp;&amp; x &lt;= <span class="string">'9'</span>) &#123;</span><br><span class="line">			n = n * <span class="number">10</span> + x - <span class="string">'0'</span>;</span><br><span class="line">			<span class="built_in">cin</span> &gt;&gt; x;</span><br><span class="line">			<span class="keyword">if</span> (! (x &gt;= <span class="string">'0'</span> &amp;&amp; x &lt;= <span class="string">'9'</span>)) &#123;</span><br><span class="line">				num.push(n);</span><br><span class="line">				n = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">cin</span>.putback(x);</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (icp(x) &lt; isp(op.top())) &#123;</span><br><span class="line">			<span class="keyword">while</span> (icp(x) &lt; isp(op.top())) &#123;</span><br><span class="line">				b = num.top();</span><br><span class="line">				num.pop();</span><br><span class="line">				a = num.top();</span><br><span class="line">				num.pop();</span><br><span class="line">				num.push(fun(a, b, op.top()));</span><br><span class="line">				op.pop();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (icp(x) &gt; isp(op.top())) &#123;</span><br><span class="line">			op.push(x);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (x == <span class="string">')'</span>) &#123;</span><br><span class="line">			op.pop();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (x == <span class="string">'#'</span>) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; num.top() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">			<span class="keyword">while</span> (! num.empty()) &#123;</span><br><span class="line">				num.pop();</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">while</span> (! op.empty()) &#123;</span><br><span class="line">				op.pop();</span><br><span class="line">			&#125;</span><br><span class="line">			op.push(<span class="string">'#'</span>);</span><br><span class="line">			n = <span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="n阶Hanoi塔问题"><a href="#n阶Hanoi塔问题" class="headerlink" title="n阶Hanoi塔问题"></a>n阶Hanoi塔问题</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iomanip&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">char</span> s1[] = &#123;<span class="string">'Y'</span>, <span class="string">'Z'</span>&#125;;	</span><br><span class="line"><span class="keyword">char</span> s2[] = &#123;<span class="string">'X'</span>, <span class="string">'Y'</span>&#125;;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">hanoi</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">char</span> from, <span class="keyword">char</span> to, <span class="keyword">char</span> xx, <span class="keyword">int</span> &amp;i)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (n == <span class="number">1</span>) &#123;</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; setw(<span class="number">2</span>) &lt;&lt; i &lt;&lt; <span class="string">". Move disk "</span> &lt;&lt; n &lt;&lt; <span class="string">" from "</span> &lt;&lt; from &lt;&lt; <span class="string">" to "</span> &lt;&lt; to &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">		i++;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	hanoi(n - <span class="number">1</span>, from, xx, to, i);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; setw(<span class="number">2</span>) &lt;&lt; i &lt;&lt; <span class="string">". Move disk "</span> &lt;&lt; n &lt;&lt;<span class="string">" from "</span> &lt;&lt; from &lt;&lt; <span class="string">" to "</span> &lt;&lt; to &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	i++;</span><br><span class="line">	hanoi(n - <span class="number">1</span>, xx, to, from, i);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; n) &#123;</span><br><span class="line">		<span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line">		hanoi(n, <span class="string">'X'</span>, <span class="string">'Z'</span>, <span class="string">'Y'</span>, i);</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="定位子串"><a href="#定位子串" class="headerlink" title="定位子串"></a>定位子串</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> str1[<span class="number">150</span>], str2[<span class="number">150</span>];</span><br><span class="line">	<span class="keyword">char</span> *s;</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; str1) &#123;</span><br><span class="line">		<span class="built_in">cin</span> &gt;&gt; str2;</span><br><span class="line">		s = <span class="built_in">strstr</span>(str1, str2);</span><br><span class="line">		<span class="keyword">if</span> (s == <span class="literal">NULL</span>)</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; <span class="number">0</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; (s - str1) / <span class="keyword">sizeof</span>(<span class="keyword">char</span>) + <span class="number">1</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="字符串插入"><a href="#字符串插入" class="headerlink" title="字符串插入"></a>字符串插入</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> s1[<span class="number">200</span>], s2[<span class="number">200</span>];</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; s1 &gt;&gt; s2 &gt;&gt; n) &#123;</span><br><span class="line">		<span class="keyword">int</span> l1 = <span class="built_in">strlen</span>(s1);</span><br><span class="line">		<span class="keyword">int</span> l2 = <span class="built_in">strlen</span>(s2);</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n - <span class="number">1</span>; i++) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; s1[i]; </span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; l2; i++) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; s2[i];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = n - <span class="number">1</span>; i &lt; l1; i++) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; s1[i];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="求子串位置的定位函数"><a href="#求子串位置的定位函数" class="headerlink" title="求子串位置的定位函数"></a>求子串位置的定位函数</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> s1[<span class="number">1000</span>],s2[<span class="number">1000</span>];</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; s1 &gt;&gt; s2) &#123;</span><br><span class="line">		<span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (; i &lt; <span class="built_in">strlen</span>(s1); i++) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; s1[i];</span><br><span class="line">			<span class="keyword">if</span> (s1[i] == s2[<span class="number">0</span>]) &#123;</span><br><span class="line">				<span class="keyword">int</span> j = <span class="number">1</span>;</span><br><span class="line">				<span class="keyword">for</span> (; j &lt; <span class="built_in">strlen</span>(s2); j++) &#123;</span><br><span class="line">					<span class="keyword">if</span> (i + j &lt; <span class="built_in">strlen</span>(s1))</span><br><span class="line">						<span class="built_in">cout</span> &lt;&lt; s1[i + j];</span><br><span class="line">					<span class="keyword">if</span> (i + j &gt;= <span class="built_in">strlen</span>(s1) || s1[i + j] != s2[j])</span><br><span class="line">						<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">if</span> (j == <span class="built_in">strlen</span>(s2)) &#123;</span><br><span class="line">					<span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span> &lt;&lt; i + <span class="number">1</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (i == <span class="built_in">strlen</span>(s1)) &#123;</span><br><span class="line">			<span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span> &lt;&lt; <span class="number">0</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="KMP算法中的模式串移动数组"><a href="#KMP算法中的模式串移动数组" class="headerlink" title="KMP算法中的模式串移动数组"></a>KMP算法中的模式串移动数组</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">get_next</span><span class="params">(<span class="keyword">char</span> *t, <span class="keyword">int</span> *next)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line">	next[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> j = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (i &lt; t[<span class="number">0</span>]) &#123;</span><br><span class="line">		<span class="keyword">if</span> (j == <span class="number">0</span> || t[i] == t[j]) &#123;</span><br><span class="line">			++i;</span><br><span class="line">			++j;</span><br><span class="line">			next[i] = j;</span><br><span class="line">		&#125;<span class="keyword">else</span></span><br><span class="line">			j = next[j];</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> s[<span class="number">105</span>],t[<span class="number">105</span>];</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span>&gt;&gt;s)&#123;</span><br><span class="line">		t[<span class="number">0</span>]=<span class="built_in">strlen</span>(s);</span><br><span class="line">		<span class="built_in">strcpy</span>(t+<span class="number">1</span>,s);</span><br><span class="line">		<span class="keyword">int</span> next[<span class="number">1000</span>];</span><br><span class="line">		get_next(t,next);</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=t[<span class="number">0</span>];i++) &#123;</span><br><span class="line">			<span class="built_in">cout</span>&lt;&lt;next[i]&lt;&lt; <span class="string">" "</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="KMP字符串模式匹配算法实现"><a href="#KMP字符串模式匹配算法实现" class="headerlink" title="KMP字符串模式匹配算法实现"></a>KMP字符串模式匹配算法实现</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SString</span>&#123;</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	<span class="keyword">char</span> *s;</span><br><span class="line">	<span class="keyword">char</span> len;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	SString(<span class="keyword">char</span> *ss) &#123;</span><br><span class="line">		<span class="built_in">set</span>(ss);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">set</span><span class="params">(<span class="keyword">char</span> *ss)</span> </span>&#123;</span><br><span class="line">		s = ss;</span><br><span class="line">		len = <span class="built_in">strlen</span>(s);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">char</span>&amp; <span class="keyword">operator</span>[](<span class="keyword">int</span> index) &#123;</span><br><span class="line">		<span class="keyword">if</span> (index == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> len;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> s[index - <span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">get_next</span><span class="params">(SString t, <span class="keyword">int</span> *next)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line">	next[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> j = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (i &lt; t[<span class="number">0</span>]) &#123;</span><br><span class="line">		<span class="keyword">if</span> (j == <span class="number">0</span> || t[i] == t[j]) &#123;</span><br><span class="line">			++i;</span><br><span class="line">			++j;</span><br><span class="line">			next[i] = j;</span><br><span class="line">		&#125;<span class="keyword">else</span></span><br><span class="line">			j = next[j];</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Index_KMP</span><span class="params">(SString S, SString T, <span class="keyword">int</span> pos)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> next[<span class="number">255</span>];</span><br><span class="line">	<span class="keyword">int</span> i = pos;</span><br><span class="line">	<span class="keyword">int</span> j = <span class="number">1</span>;</span><br><span class="line">	get_next(T, next);</span><br><span class="line">	<span class="keyword">while</span> (i &lt;= S[<span class="number">0</span>] &amp;&amp; j &lt;= T[<span class="number">0</span>]) &#123;</span><br><span class="line">		<span class="keyword">if</span> (j == <span class="number">0</span> || S[i] == T[j]) &#123;</span><br><span class="line">			++i;</span><br><span class="line">			++j;</span><br><span class="line">		&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">			j = next[j];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (j &gt; T[<span class="number">0</span>])</span><br><span class="line">		<span class="keyword">return</span> i - T[<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">char</span> s1[<span class="number">105</span>], s2[<span class="number">105</span>];</span><br><span class="line">	<span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; s1 &gt;&gt; s2) &#123;</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; Index_KMP(SString(s1), SString(s2), <span class="number">1</span>) &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="稀疏矩阵转置"><a href="#稀疏矩阵转置" class="headerlink" title="稀疏矩阵转置"></a>稀疏矩阵转置</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iomanip&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">struct</span> <span class="title">Trituple</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> row;</span><br><span class="line">    <span class="keyword">int</span> col;</span><br><span class="line">    T val;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">class</span> <span class="title">SparseMatrix</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    SparseMatrix(<span class="keyword">int</span> maxt=<span class="number">100</span>);</span><br><span class="line">    ~SparseMatrix();</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">TransposeTo</span><span class="params">(SparseMatrix &amp;)</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">AddTo</span><span class="params">(<span class="keyword">const</span> SparseMatrix&amp;)</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Input</span><span class="params">()</span></span>;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Output</span><span class="params">()</span></span>;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    Trituple&lt;T&gt;* data;</span><br><span class="line">    <span class="keyword">int</span> rows,cols,terms;</span><br><span class="line">    <span class="keyword">int</span> maxterms;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">SparseMatrix</span>&lt;T&gt;:</span>:SparseMatrix(<span class="keyword">int</span> maxt)</span><br><span class="line">&#123;</span><br><span class="line">    maxterms=maxt;</span><br><span class="line">    data=<span class="keyword">new</span> Trituple&lt;T&gt;[maxterms];</span><br><span class="line">    terms=rows=cols=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">SparseMatrix</span>&lt;T&gt;:</span>:~SparseMatrix()</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (data!=<span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">delete</span>[] data;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">bool</span> <span class="title">SparseMatrix</span>&lt;T&gt;:</span>:TransposeTo(SparseMatrix &amp;B)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (terms&gt;B.maxterms)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    B.rows=cols;</span><br><span class="line">    B.cols=rows;</span><br><span class="line">    B.terms=terms;</span><br><span class="line">    <span class="keyword">if</span> (terms&gt;<span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> p=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=cols;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k=<span class="number">0</span>;k&lt;terms;k++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span> (data[k].col==j)</span><br><span class="line">                &#123;</span><br><span class="line">                    B.data[p].row=j;</span><br><span class="line">                    B.data[p].col=data[k].row;</span><br><span class="line">                    B.data[p].val=data[k].val;</span><br><span class="line">                    p++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">void</span> <span class="title">SparseMatrix</span>&lt;T&gt;:</span>:Input()</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">int</span> row1,col1,number;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;row1&gt;&gt;col1;</span><br><span class="line">    rows=row1;</span><br><span class="line">    cols=col1;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;rows;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;cols;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">cin</span>&gt;&gt;number;</span><br><span class="line">            <span class="keyword">if</span> (number!=<span class="number">0</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                data[terms].row=i+<span class="number">1</span>;</span><br><span class="line">                data[terms].col=j+<span class="number">1</span>;</span><br><span class="line">                data[terms].val=number;</span><br><span class="line">                terms++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">void</span> <span class="title">SparseMatrix</span>&lt;T&gt;:</span>:Output()</span><br><span class="line">&#123;</span><br><span class="line">    T **tempArray=<span class="keyword">new</span> T*[rows];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i1=<span class="number">0</span>;i1&lt;rows;i1++)</span><br><span class="line">    &#123;</span><br><span class="line">        tempArray[i1]=<span class="keyword">new</span> <span class="keyword">int</span>[cols];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;rows;j++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k=<span class="number">0</span>;k&lt;cols;k++)</span><br><span class="line">        &#123;</span><br><span class="line">            tempArray[j][k]=<span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;terms;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        tempArray[data[i].row<span class="number">-1</span>][data[i].col<span class="number">-1</span>]=data[i].val;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;rows;j++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k=<span class="number">0</span>;k&lt;cols;k++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">cout</span>&lt;&lt;tempArray[j][k]&lt;&lt;<span class="string">" "</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> l=<span class="number">0</span>;l&lt;rows;l++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">delete</span>[] tempArray[l];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">delete</span> tempArray;</span><br><span class="line">    <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span>&lt;<span class="class"><span class="keyword">class</span> <span class="title">T</span>&gt;</span></span><br><span class="line"><span class="class"><span class="title">bool</span> <span class="title">SparseMatrix</span>&lt;T&gt;:</span>:AddTo(<span class="keyword">const</span> SparseMatrix&amp; B)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (rows!=B.rows||cols!=B.cols)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">bool</span> flag=<span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">int</span> tempTerms=terms;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;B.terms;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        flag=<span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;tempTerms;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (data[j].col==B.data[i].col&amp;&amp;data[j].row==B.data[i].row)</span><br><span class="line">            &#123;</span><br><span class="line">                data[j].val+=B.data[i].val;</span><br><span class="line">                flag=<span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (flag==<span class="literal">false</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            data[++terms<span class="number">-1</span>].col=B.data[i].col; </span><br><span class="line">            data[terms<span class="number">-1</span>].row=B.data[i].row;</span><br><span class="line">            data[terms<span class="number">-1</span>].val=B.data[i].val;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    SparseMatrix&lt;<span class="keyword">int</span>&gt; sm(<span class="number">50</span>);</span><br><span class="line">    SparseMatrix&lt;<span class="keyword">int</span>&gt; sm1(<span class="number">50</span>);</span><br><span class="line">    SparseMatrix&lt;<span class="keyword">int</span>&gt; sm2(<span class="number">50</span>);</span><br><span class="line">    sm.Input();</span><br><span class="line">    sm.TransposeTo(sm1);</span><br><span class="line">    sm1.Output();</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="稀疏矩阵快速转置"><a href="#稀疏矩阵快速转置" class="headerlink" title="稀疏矩阵快速转置"></a>稀疏矩阵快速转置</h2><blockquote>
<p>这道题我提交了十次才AC。。。。</p>
</blockquote>
<figure class="highlight mipsasm"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#include&lt;iostream&gt;</span></span><br><span class="line">using namespace std<span class="comment">;</span></span><br><span class="line"><span class="comment">#define MAXROW 250</span></span><br><span class="line"><span class="comment">#define MAXSIZE 12500</span></span><br><span class="line">typedef int ElemType<span class="comment">;</span></span><br><span class="line">typedef struct</span><br><span class="line">&#123;</span><br><span class="line">	int i, <span class="keyword">j;</span></span><br><span class="line"><span class="keyword">	</span>ElemType e<span class="comment">;</span></span><br><span class="line">&#125;Triple<span class="comment">;</span></span><br><span class="line">typedef struct</span><br><span class="line">&#123;</span><br><span class="line">	Triple data[MAXSIZE + <span class="number">1</span>]<span class="comment">;</span></span><br><span class="line">	int n, m, t<span class="comment">;</span></span><br><span class="line">&#125;Matrix<span class="comment">;</span></span><br><span class="line">void <span class="keyword">Inst(Matrix </span>&amp;a)</span><br><span class="line">&#123;</span><br><span class="line">	int i, <span class="keyword">j;</span></span><br><span class="line"><span class="keyword">	</span>ElemType tmp<span class="comment">;</span></span><br><span class="line">	cin&gt;&gt;a.n&gt;&gt;a.m<span class="comment">;</span></span><br><span class="line">	a.t = <span class="number">0</span><span class="comment">;</span></span><br><span class="line">	for (i = <span class="number">1</span><span class="comment">; i &lt;= a.n; i++)</span></span><br><span class="line">	&#123;</span><br><span class="line">		for (<span class="keyword">j </span>= <span class="number">1</span><span class="comment">; j &lt;= a.m; j++)</span></span><br><span class="line">		&#123;</span><br><span class="line">			cin&gt;&gt;tmp<span class="comment">;</span></span><br><span class="line">			if (tmp)</span><br><span class="line">			&#123;</span><br><span class="line">				a.t++<span class="comment">;</span></span><br><span class="line">				a<span class="meta">.data</span>[a.t].i = i<span class="comment">;</span></span><br><span class="line">				a<span class="meta">.data</span>[a.t].<span class="keyword">j </span>= <span class="keyword">j;</span></span><br><span class="line"><span class="keyword">	</span>			a<span class="meta">.data</span>[a.t].e = tmp<span class="comment">;</span></span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">void Trans(Matrix a, Matrix &amp;<span class="keyword">b)</span></span><br><span class="line"><span class="keyword">&#123;</span></span><br><span class="line"><span class="keyword">	</span>int num[MAXROW + <span class="number">1</span>] = &#123; <span class="number">0</span> &#125;, pos[MAXROW + <span class="number">1</span>] = &#123; <span class="number">0</span> &#125;<span class="comment">;</span></span><br><span class="line">	int i, <span class="keyword">j, </span>p<span class="comment">;</span></span><br><span class="line">	<span class="keyword">b.n </span>= a.m<span class="comment">; b.m = a.n; b.t = a.t;</span></span><br><span class="line">	for (i = <span class="number">1</span><span class="comment">; i &lt;= a.t; i++) num[a.data[i].j]++;</span></span><br><span class="line">	for (i = <span class="number">1</span><span class="comment">; i &lt;= a.m; i++) pos[i] = pos[i - 1] + num[i];</span></span><br><span class="line">	for (i = a.t<span class="comment">; i &gt;= 1; i--)</span></span><br><span class="line">	&#123;</span><br><span class="line">		p = pos[a<span class="meta">.data</span>[i].<span class="keyword">j]--;</span></span><br><span class="line"><span class="keyword">	</span>	<span class="keyword">b.data[p].i </span>= a<span class="meta">.data</span>[i].<span class="keyword">j;</span></span><br><span class="line"><span class="keyword">	</span>	<span class="keyword">b.data[p].j </span>= a<span class="meta">.data</span>[i].i<span class="comment">;</span></span><br><span class="line">		<span class="keyword">b.data[p].e </span>= a<span class="meta">.data</span>[i].e<span class="comment">;</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">void Out(Matrix a)</span><br><span class="line">&#123;</span><br><span class="line">	int i, <span class="keyword">j;</span></span><br><span class="line"><span class="keyword">	</span>int u = <span class="number">1</span><span class="comment">;</span></span><br><span class="line">	for (i = <span class="number">1</span><span class="comment">; i &lt;= a.n; i++)</span></span><br><span class="line">	&#123;</span><br><span class="line">		for (<span class="keyword">j </span>= <span class="number">1</span><span class="comment">; j &lt;= a.m; j++)</span></span><br><span class="line">		if (i == a<span class="meta">.data</span>[u].i &amp;&amp; <span class="keyword">j </span>== a<span class="meta">.data</span>[u].<span class="keyword">j)</span></span><br><span class="line"><span class="keyword">	</span>		cout&lt;&lt;a<span class="meta">.data</span>[u++].e&lt;&lt;<span class="string">" "</span><span class="comment">;</span></span><br><span class="line">		else</span><br><span class="line">			cout&lt;&lt;<span class="string">"0"</span>&lt;&lt;<span class="string">" "</span><span class="comment">;</span></span><br><span class="line">		cout&lt;&lt;endl<span class="comment">;</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	Matrix a, <span class="keyword">b;</span></span><br><span class="line"><span class="keyword">	</span><span class="keyword">Inst(a);</span></span><br><span class="line"><span class="keyword">	</span>Trans(a, <span class="keyword">b);</span></span><br><span class="line"><span class="keyword">	</span>Out(<span class="keyword">b);</span></span><br><span class="line"><span class="keyword">	</span>return <span class="number">0</span><span class="comment">;</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>

    
      
      



      
      
    

    
      <footer class="post-footer">
        
          <div class="post-tags">
            
              <a href="/tags/c/">c++</a>
            
              <a href="/tags/算法/">算法</a>
            
              <a href="/tags/OJ/">OJ</a>
            
          </div>
        
        
        
  <nav class="post-nav">
    
      <a class="prev" href="/2017/05/31/Hexo可视化编写相关设置/">
        <i class="iconfont icon-left"></i>
        <span class="prev-text nav-default">Hexo可视化编写和文章加密设置</span>
        <span class="prev-text nav-mobile">上一篇</span>
      </a>
    
    
      <a class="next" href="/2017/05/19/Mysql安装和操作-flask/">
        <span class="next-text nav-default">Mysql安装和操作(flask)</span>
        <span class="prev-text nav-mobile">下一篇</span>
        <i class="iconfont icon-right"></i>
      </a>
    
  </nav>

      </footer>
    

  </article>


          </div>
          
  <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="//disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div> 
    </div>
  </div>


        </div>
      </main>

      <footer id="footer" class="footer">

  <div class="social-links">
    
      
        
          <a href="https://github.com/bay1" class="iconfont icon-github" title="github"></a>
        
      
    
      
        
          <a href="http://weibo.com/3190704711/profile?topnav=1&wvr=6&is_all=1" class="iconfont icon-weibo" title="weibo"></a>
        
      
    
      
    
      
    
      
    
    
    
  </div>


<div class="copyright">
  <span class="copyright-year">
    
    &copy; 
     
      2016 - 
    
    2018
    <span class="author">bay1</span>
  </span>
</div>
      </footer>

      <div class="back-to-top" id="back-to-top">
        <i class="iconfont icon-up"></i>
      </div>
    </div>

    
  
  <script type="text/javascript">
    var disqus_config = function () {
        this.page.url = 'https://bay1.top/2017/05/27/痛苦的数据结构OJ续/';
        this.page.identifier = '2017/05/27/痛苦的数据结构OJ续/';
        this.page.title = '痛苦的数据结构OJ续';
    };
    (function() {
    var d = document, s = d.createElement('script');

    s.src = '//https-blog-flywinky-top-1.disqus.com/embed.js';

    s.setAttribute('data-timestamp', +new Date());
    (d.head || d.body).appendChild(s);
    })();  
  </script>



    
  





  
    <script type="text/javascript" src="/lib/jquery/jquery-3.1.1.min.js"></script>
  

  
    <script type="text/javascript" src="/lib/slideout/slideout.js"></script>
  

  
    <script type="text/javascript" src="/lib/fancybox/jquery.fancybox.pack.js"></script>
  


    <script type="text/javascript" src="/js/src/even.js?v=2.6.0"></script>
<script type="text/javascript" src="/js/src/bootstrap.js?v=2.6.0"></script>
<script src="/js/prettify.js"></script>
<script type="text/javascript">
$(document).ready(function(){
 $('pre').addClass('prettyprint');
   prettyPrint();
 })
</script>
  </body>
</html>
